//前言:红黑树:也是一种搜索二叉树,但是在每个结点上都增加一个存储位表示结点的颜色,可以是 red 或 black.通过对任何一条从根到叶子路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍
//--.红黑树是接近平衡的          avl 树是严格平衡的
//---红黑树比 avl 树更常用,也就是说大部分使用的这种搜索二叉树,
//---红黑树的重点就是控制颜色    一定要记住这个平衡是接近平衡,avl 树是严格平衡
//---严格要记住黑色结点的数量是相同的







//一丶  红黑树的基本概念
//1.红黑树的性质                  -----一共五条性质
//ps1:每个结点不是红色就是黑色
//ps2:根结点是黑色的
//ps3:如果一个结点是红色的则它的两个孩子结点是黑色的                   ------但是两个连续的黑色结点是允许的,黑色结点的子结点可以是黑色,允许黑色的结点有一黑一红两个子结点
//ps4:对于每个结点,从该结点到其所有后代叶节点的简单路径中,均包含相同数目的黑色结点
//---这句话的意思是:每条路径上黑色结点的数量是相等的

//ps5:每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
//也就是最后末尾存放元素的结点,在后面都有两个只存放黑色但是不存放元素的空结点,----此处的叶子结点并不是传统意义上的叶子结点,也叫 nil 结点

//---顺便思考一下,为什么满足上面的性质,红黑树就能保证:其最长路径中结点个数不会超过最短路径结点个数的两倍?
//---这是因为最短路径大不了是全黑,但是最长路径是一黑一红的结点.  又因为从某个结点开始,其子路径的黑结点的数量是相同的,红结点的后面必须是黑的.
//---也就是说  最长路径:一黑一红      最短路径:全黑        N<=任意路径长度<=2N   (N 是路径上的黑色结点个数,包括这个黑色的结点)

//---上面的重点是第三点和第四点






//2.avl 树和红黑树的对比
//ps1:avl 树是的两边更接近均衡,高度更接近 log2 N     在满二叉树的情况下:2^h-1=N             稍微不满足平衡的时候,就会发生旋转
//ps2:红黑树的左右两边没有那么均衡,但是红黑树的旋转是发生在最长路径超过了最短路径的二倍,(在没有超过的时候也可能发生旋转,但是超过了最短路径一定会发生旋转
//ps3:红黑树的高度:我们假设红黑树中一条路径黑色结点的数量是 x,则红黑树的高度h是  2x>=h>=x  ,         红黑树的所有的结点的数量 2^x-1<=N<=2^2x-1

//ps4:avl 树是严格平衡的,增删查改的效率是 logN       红黑树是近似平衡的,效率是 2*logN                但是为什么红黑树经常使用,因为这两个对于 cpu 来说,搜索级别没什么区别










//二丶 对自己实现的红黑树进行测试
#include"12_红黑树的实现.h"

void testRBTree()
{
    RBTree<int,int> rb;
    int arr[]={1,3,5,7,9,2,4,6,8,10};
    for(auto e:arr)
    {
        rb.insert(make_pair(e,e));
    }
    rb.inorder();

    cout<<rb.isbalance()<<endl;
}

int main(void)
{
    testRBTree();
}
